package _08_动态规划;

import java.util.Arrays;

/*
    凑零钱
 */
public class Coins {

    //dp(i) 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
    int coinChangeDP(int[] coins,int amount){
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount + 1);

        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for(int i=1;i<dp.length;++i){
            // 内层 for 循环在求所有选择的最小值
            for(int coin:coins){
                if(i<coin) continue;
                dp[i] = Math.min(dp[i],dp[i-coin] + 1);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

    int[] memo;
    int coinChange(int[] coins,int amount){
        memo = new int[amount + 1];
        Arrays.fill(memo,999);
        return dp(coins,amount);
    }

    //dp(i):凑够i分钱所需要的最少硬币
    int dp(int[] coins,int amount){
        //base case
        if(amount == 0) return 0;
        if(amount<0) return -1;
        if(memo[amount] != 999){ //查看备忘录，防止重复计算
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins) { //每个选择
            //计算每个子问题的解
            int sub = dp(coins,amount - coin);
            if(sub == -1) continue; //子问题无解跳过
            res = Math.min(res,sub+1); //在子问题中选择最优解，然后加1
        }
        //把计算结果存入备忘录
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}
